/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 vector_set.h

	$Header: /heroes4/vector_set.h $

	$NoKeywords: $

 ************************************************************************/

#if !defined( VECTOR_SET_H_INCLUDED )
#define VECTOR_SET_H_INCLUDED

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <algorithm>
#include <functional>
#include <memory>
#include <set>
#include <utility>
#include <vector>

// ------------------------------------------------------------------------------
// t_vector_set class template
// ------------------------------------------------------------------------------

template <
	typename t_key_arg,
	typename t_key_compare_arg = std::less< t_key_arg >,
	typename t_allocator_arg = std::allocator< t_key_arg > >
class t_vector_set : private t_key_compare_arg
{
private:
	// Types
	typedef	std::vector<
				t_key_arg,
				t_allocator_arg >	t_impl_;

public:
	// Types
	typedef typename t_key_arg							key_type;
	typedef typename t_key_compare_arg					key_compare;
	typedef typename t_key_arg							value_type;
	typedef typename t_key_compare_arg					value_compare;
	typedef typename t_impl_::allocator_type			allocator_type;
	typedef typename t_impl_::size_type					size_type;
	typedef typename t_impl_::difference_type			difference_type;
	typedef typename t_impl_::const_reference			reference;
	typedef typename t_impl_::const_reference			const_reference;
	typedef typename t_impl_::const_iterator			iterator;
	typedef typename t_impl_::const_iterator			const_iterator;
	typedef typename t_impl_::const_reverse_iterator	reverse_iterator;
	typedef typename t_impl_::const_reverse_iterator	const_reverse_iterator;

private:
	// Types
	typedef std::pair< const_iterator, const_iterator >	t_equal_range_result;
	typedef std::pair< iterator, bool >					t_insert_result;

public:

	// Constructors
	explicit t_vector_set(
		key_compare const &		compare = key_compare(),
		allocator_type const &	alloc = allocator_type() )
		:	key_compare( compare ),
			m_impl( alloc )
	{
	}

	template < typename t_input_iter >
	t_vector_set(
		t_input_iter			first,
		t_input_iter			last,
		key_compare const &		compare = key_compare(),
		allocator_type const &	alloc = allocator_type() )
		:	key_compare( compare ),
			m_impl( alloc )
	{
		while ( first != last )
			insert( *first++ );
	}

	t_vector_set(
		std::set< t_key_arg, t_key_compare_arg, t_allocator_arg > const & other );

	// Member functions
	const_iterator			begin() const
								{ return m_impl.begin(); }
	size_type				capacity() const
								{ return m_impl.capacity(); }
	void					clear()
								{ m_impl.clear(); }
	size_type				count( key_type const & key ) const;
	bool					empty() const
								{ return m_impl.empty(); }
	const_iterator			end() const
								{ return m_impl.end(); }
	t_equal_range_result	equal_range( key_type const & key ) const;
	iterator				erase( iterator iter );
	iterator				erase( iterator first, iterator last );
	size_type				erase( key_type const & key );
	const_iterator			find( key_type const & key ) const;
	allocator_type			get_allocator() const
								{ return m_impl.get_allocator(); }
	t_insert_result			insert( value_type const & value );
	iterator				insert( iterator hint, value_type const & value );
	template < typename t_input_iter >
	void					insert( t_input_iter first, t_input_iter last )
								{ while ( first != last ) insert( *first++ ); }
	key_compare				key_comp() const
								{ return *this; }
	const_iterator			lower_bound( key_type const & key ) const;
	size_type				max_size() const
								{ return m_impl.max_size(); }
	const_reverse_iterator	rbegin() const
								{ return m_impl.rbegin(); }
	const_reverse_iterator	rend() const
								{ return m_impl.rend(); }
	void					reserve( size_type new_capacity )
								{ m_impl.reserve( new_capacity ); }
	size_type				size() const
								{ return m_impl.size(); }
	void					swap( t_vector_set & other );
	const_iterator			upper_bound( key_type const & key ) const;
	value_compare			value_comp() const
								{ return *this; }

	// Operators
	const_reference			operator[]( size_type index ) const
								{ return m_impl[ index ]; }
							operator
								std::set<
									t_key_arg,
									t_key_compare_arg,
									t_allocator_arg >() const;

private:
	// Data members
	t_impl_		m_impl;
};

// ------------------------------------------------------------------------------
// t_vector_set members
// ------------------------------------------------------------------------------

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::t_vector_set(
	std::set< t_key_arg, t_key_compare_arg, t_allocator_arg > const & other )
	:	key_compare( other.key_comp() ),
		m_impl( other.get_allocator() )
{
	m_impl.reserve( other.size() );
	std::copy( other.begin(), other.end(), std::back_inserter( m_impl ) );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::size_type
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::count(
	key_type const & key ) const
{
	t_equal_range_result equal_range_result = equal_range( key );
	return equal_range_result.second - equal_range_result.first;
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::t_equal_range_result
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::equal_range(
	key_type const & key ) const
{
	return std::equal_range( m_impl.begin(), m_impl.end(), key, key_comp() );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::erase(
	iterator iter )
{
	t_impl_::iterator impl_begin = m_impl.begin();
	return m_impl.erase( impl_begin + ( iter - impl_begin ) );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::erase(
	iterator	first,
	iterator	last )
{
	t_impl_::iterator impl_begin = m_impl.begin();
	t_impl_::iterator impl_first = impl_begin + ( first - impl_begin );
	t_impl_::iterator impl_last = impl_begin + ( last - impl_begin );
	return m_impl.erase( impl_first, impl_last );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::size_type
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::erase(
	key_type const & key )
{
	t_equal_range_result equal_range_result = equal_range( key );
	size_type result = equal_range_result.second - equal_range_result.first;
	erase( equal_range_result.first, equal_range_result.second );
	return result;
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::const_iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::find(
	key_type const & key ) const
{
	const_iterator last = end();
	const_iterator iter = lower_bound( key );
	if ( iter == last || !key_comp()( key, *iter ) )
		return iter;
	return last;
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::t_insert_result
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::insert(
	value_type const & value )
{
	const_iterator iter = lower_bound( value );
	bool inserted;
	if ( iter == end() || key_comp()( value, *iter ) )
	{
		t_impl_::iterator impl_begin = m_impl.begin();
		iter = m_impl.insert( impl_begin + ( iter - impl_begin ), value );
		inserted = true;
	}
	else
		inserted = false;
	return t_insert_result( iter, inserted );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::insert(
	iterator			hint,
	value_type const &	value )
{
	// For now just ignore the hint
	return insert( value ).first;
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::const_iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::lower_bound(
	key_type const & key ) const
{
	return std::lower_bound( m_impl.begin(), m_impl.end(), key, key_comp() );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline void
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::swap(
	t_vector_set & other )
{
	std::swap(
		static_cast< key_compare & >( *this ),
		static_cast< key_compare & >( other ) );
	m_impl.swap( other.m_impl );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
inline
typename t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::const_iterator
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::upper_bound(
	key_type const & key ) const
{
	return std::upper_bound( m_impl.begin(), m_impl.end(), key, key_comp() );
}

// ------------------------------------------------------------------------------
// ------------------------------------------------------------------------------
template <
	typename t_key_arg,
	typename t_key_compare_arg,
	typename t_allocator_arg >
t_vector_set< t_key_arg, t_key_compare_arg, t_allocator_arg >::operator
	std::set< t_key_arg, t_key_compare_arg, t_allocator_arg >() const
{
	typedef std::set< t_key_arg, t_key_compare_arg, t_allocator_arg > t_result;
	t_result result( key_comp(), get_allocator() );
	t_impl_::const_iterator impl_end = m_impl.end();
	t_impl_::const_iterator impl_iter = m_impl.begin();
	for ( ; impl_iter != impl_end; ++impl_iter )
		result.insert( result.end(), *impl_iter );
	return result;
}

#endif // !defined( VECTOR_SET_H_INCLUDED )
